// leetcode.algorithms.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <stack>
#include <queue>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <string>

using namespace std;

class sort_solution
{
public:
  void mergeLarge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int s1 = 0, s2 = 0, i = 0;
    vector<int> out(nums1.size());
    while (s1 != m && s2 != n) {
      if (nums1[s1] <= nums2[s2]) {
        out[i] = nums1[s1];
        s1++;
      }
      else {
        out[i] = nums2[s2];
        s2++;
      }
      i++;
    }
    if (s1 == m) {
      for (int j = s2; j < n; j++) {
        out[s1 + j] = nums2[j];
      }
    }
    if (s2 == n) {
      for (int j = s1; j < m; j++) {
        out[s2 + j] = nums1[j];
      }
    }
    nums1 = out;
  }

  void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int s1 = 0, s2 = 0, i = 0;
    vector<int> out(nums1.size());
    while (s1 != m && s2 != n) {
      if (nums1[s1] <= nums2[s2]) {
        out[i] = nums1[s1];
        s1++;
      }
      else {
        out[i] = nums2[s2];
        s2++;
      }
      i++;
    }
    if (s1 == m) {
      for (int j = s2; j < n; j++) {
        out[s1 + j] = nums2[j];
      }
    }
    if (s2 == n) {
      for (int j = s1; j < m; j++) {
        out[s2 + j] = nums1[j];
      }
    }
    nums1 = out;
  }

  bool isBadVersion(int v)
  {
  }

  int firstBadVersion(int n) {
    if (n == 1) return 1;
    int low = 0, mid = 0;
    while (low < n) {
      mid = low + (n - low) / 2;
      if (!isBadVersion(mid)) {
        low = mid + 1;
      }
      else {
        n = mid;
      }
    }
    return low;
  }

  int firstUniqChar(string s) {
    int start, pos, size = s.size();
    bool find = false;
    for (start = 0; start < size; start++) {
      for (pos = 0; pos < size; pos++) {
        if (start == pos) continue;
        if (s[start] == s[pos]) find = true;
      }
      if (!find) return start;
      find = false;
    }
    return -1;
  }

  int countPrimes(int n) {
    vector<bool> arr(n);
    int cnt = 0;
    for (int i = 2; i < n; i++) {
      if (arr[i]) continue;
      cnt++;
      for (int j = i; j < n; j += i) {
        arr[j] = true;
      }
    }
    return cnt;
  }

  vector<string> fizzBuzz(int n) {
    vector<string> out;
    for (int i = 1; i <= n; i++) {
      if (i % 3 == 0 && i % 5 == 0) {
        out.push_back("FizzBuzz");
        continue;
      }
      if (i % 5 == 0) {
        out.push_back("Buzz");
        continue;
      }
      if (i % 3 == 0) {
        out.push_back("Fizz");
        continue;
      }
      out.push_back(std::to_string(i));
    }
    return out;
  }
};